package ustc.xiaoyang.karl.slidingwindows;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 438.找到字符串中的所有字母异位词 medium
 */
public class AllAnagram438 {
    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        System.out.println(findAnagrams(s, p));
    }
    public static List<Integer> findAnagrams(String s, String p) {
        //定长滑动窗口问题
        int m = s.length();
        int n = p.length();
        //1.初始化hash数组，统计字符出现次数
        int[] cnt_s = new int[26];
        int[] cnt_p = new int[26];
        //遍历字符串统计字符次数
        for(char t : p.toCharArray()){
            cnt_p[t-'a']++;
        }
        //2.移动窗口，寻找异位词子串
        int l = -1;
        for(int i = 0; i < n - 1; i++){
            cnt_s[s.charAt(i) - 'a']++;
        }

        List<Integer> res = new ArrayList<>();
        for(int r = n - 1; r < m; r++){
            cnt_s[s.charAt(r)-'a']++;
            if(r > n - 1) cnt_s[s.charAt(l) - 'a']--;
            l++;
            if(Arrays.equals(cnt_p,cnt_s)) res.add(l);
        }
        return res;

    }
}
